1. Field of the Invention
The present invention relates to mobile robots, and, more particularly, to mapping techniques that are used with mobile robots.
2. Description of the Related Art
Automatic map building of environments, particularly indoor environments, is a basic issue of mobile robotics. Digital two-dimensional and three-dimensional models of the environment are needed in all applications with autonomous mobile robots. If a robot were to have an a priori map, then localization would be a relatively easy task. Alternatively, if the robot were to have a precise, externally referenced position estimate, then mapping would be an easy task. However, problems in which the robot has no a priori map and no external position reference are particularly challenging. Such scenarios may arise for autonomous underwater vehicles (AUVs), mining applications, or planetary surfaces.
The process of robotic mapping involves acquiring spatial models of physical environments via the use of, and for the use of, mobile robots. Maps are often used for robot navigation, such as for localization, and in many other application areas. Robotic mapping techniques without external position reference are generally referred to as SLAM (simultaneous localization and mapping) or CML (concurrent mapping and localization).
Robots are known to include sensors that detect the positions of objects and terrain encountered by the robot as it travels. The sensor may measure the distance between the robot and some object, or between the robot and the surface on which the robot is traveling. These sensor readings are made and recorded relative to the body of the robot. However, the location and orientation of the robot at any given time cannot be precisely determined. If the poses and localization (i.e., orientation and location) of a robot were known, the local outputs of the robot's sensor could be registered into a common coordinate system to create a map. Unfortunately, any mobile robot's determination of its own localization is liable to be imprecise. Because the robot is unable to determine where it is and what its orientation is precisely, its ability to create a map is limited. Moreover, because the robot cannot create an accurate map, its ability to determine its own location and orientation is also limited.
Early work in SLAM assumed that a map used for mobile robots could be modeled as a discrete set of landmarks. Different kinds of representations, or maps, have been proposed in the robotics and artificial intelligence literature. These representations, or maps, range from low-level metric maps, such as landmark maps and occupancy grids, to topological graphs that contain high level qualitative information, or even multiple hierarchies of successively higher level abstractions.
Traditionally, SLAM implementations based on Kalman filter data fusion have relied on simple geometric models for defining landmarks. This limits landmark based algorithms to environments suited to such models and tends to discard a lot of potentially useful data. Only more recently, Nieto et al. showed how to define landmarks composed of raw sensed data.
A limitation of almost all SLAM algorithms lies in the necessity to select appropriate landmarks. By reducing the sensor data to the presence of landmarks, a lot of information originally retrieved by a sensor is usually discarded.
Another problem that arises from using discrete landmarks in SLAM is the problem of data association. Before fusing data into the map, new measurements are associated with existing map landmarks, which has been proven crucial in practical SLAM implementations.
Yet another problem is that all map representations used in current SLAM-based approaches assume a random structure on the map or on the features in the map. In actuality, this is rarely the case, as man-made structures are generally highly structured. The insides of buildings, which are common workplaces for mobile robots, are typically constructed with well known methodology.
What is neither disclosed nor suggested in the art is a robotic mapping method that overcomes the above-described problems with known mapping methods.
Known SLAM methods can be described in mathematical terms presented hereinbelow. In this context, the methods of the present invention described herein may be more easily described and understood.
Known SLAM methods have been designed with the goal of simultaneously estimating both the robot's pose and the map. A SLAM algorithm creates a map while at the same time it estimates the position of the robot inside the map. When a robot operates inside of a building, planar two-dimensional maps are usually sufficient. If, however, a robot has to operate with additional degrees of freedom, then a three-dimensional map may need to be constructed.
At a time t, the following quantities are defined:                xt: A vector describing the position and orientation of the robot.        ut: The control vector that was applied at time t−1 and carries information about the change of the robot's pose.        ztk: The observations taken from the robot of the kth feature.        ctk: A correspondence variable between the kth feature and the ith landmark.        m: A vector of features m={mi} representing the environment around the robot.        
A more detailed definition of these quantities in the context of a probabilistic model is provided hereinbelow. In probabilistic SLAM, this is often posed as Bayesian filtering formulation. Two main forms of such a formulation exist. One is known as the “online SLAM problem”:p(xt,m|u1:t,z1:t,c1:t)  (1)
It involves estimating the posterior over the momentary pose xt along with the map m. It is called “online” because it involves only estimating quantities at the time t. In contrast, the “full SLAM problem” seeks to calculate a posterior over all quantities:p(x1:t,m|u1:t,z1:t,c1:t)  (2)
The full SLAM problem is focused on herein in order to simplify the further discussion. A closed form expression of Equation (2) can be obtained by recursively applying Bayes' Rule and subsequent induction over t:p(x1:t,m|u1:t,z1:t,c1:t)=ηp(x0)p(m)Πt[p(xt|xt-1,ut)Πip(zti|xt,m,cti)]  (3)
Here p(xt|xt-1,ut) is known as the “motion model” which describes state transitions of the robot's pose in terms of a probability distribution. The state transitions are assumed to be a Markov process and independent of both the observations and the map. The term p(zti|xt,m,cti) on the other hand denotes an “observation model” which models an observation zti from a known pose and a known map as a probability distribution. Both models have been studied well for a variety of robots and sensors. The two prior terms p(x0) and p(m) characterize priors about the first robot pose and about the map, respectively. Usually p(x0) is used to anchor the initial pose to a fixed location. The map prior p(m) is typically assumed to be unknown and subsumed into the normalizer η. The process of finding the most probable solution to the full SLAM problem is simply the process of finding the set of poses {circumflex over (x)}1:t and the map {circumflex over (m)} that maximizes the posterior probability of Equation (3).
                                          x            ^                                l            :            t                          ,                              m            ^                    =                                    argmax                                                x                                      l                    :                    t                                                  ,                m                                      ⁢                          p              ⁡                              (                                                      x                                          l                      :                      t                                                        ,                                      m                    ❘                                          u                                              l                        :                        t                                                                              ,                                      z                                          l                      :                      t                                                        ,                                      c                                          l                      :                      t                                                                      )                                                                        (        4        )            
A graphical model of this formulation is illustrated in FIG. 1a which shows the Bayes network of traditional landmark based SLAM. Each observation ztk is associated with a map feature mi. The non-divergence property is achieved since map features are observed from several locations. Correlations between map features are not considered.